"""****************************************************************************************
 ** FileName:       rsa_math.py
 ** Author:         Jiawei Hawkins
 ** Date:           2019-05-07 星期二 11:19:05
 ** Description:    实现rsa所需要的数学基础
 ****************************************************************************************"""

"""****************************************************************************************
 ** Date:           2019-05-07 星期二 11:22:25
 ** Description:    设RSA的模数为nbit，则实际的分组为n-1bit
 ****************************************************************************************"""
from random import randint

"""****************************************************************************************
 ** Date:           2019-05-07 星期二 11:32:51
 ** Description:    欧几里得拓展算法
 ****************************************************************************************"""
def euc_ext(a, b):                     
    if( b == 0):
        return (1, 0, a)
    x_pre = 1
    x = 0
    y_pre = 0
    y = 1
    q = int( a // b)
    tmp = a - q * b
    while( tmp != 0):
        a = b
        b = tmp

        tmp = x_pre - q * x
        x_pre = x
        x = tmp

        tmp = y_pre - q * y
        y_pre = y
        y = tmp

        q = int(a // b)
        tmp = a - q * b
    return (x, y, b)


"""****************************************************************************************
 ** Date:           2019-05-07 星期二 11:32:51
 ** Description:    快速幂算法
 ****************************************************************************************"""
def qexp(exp, n, mod):
    if( exp < 2):
        return exp
    else:
        base = exp
        ans = 1
        while (n > 0):
            if (n & 1 == 1):
                ans = (ans * base) % mod
            base = (base * base) % mod
            n = n >> 1
        return ans


"""****************************************************************************************
 ** Date:           2019-05-07 星期二 11:32:51
 ** Description:    素数检测Miller
 ****************************************************************************************"""
def miller(n):                      #Miller-Rabin素性检验算法
    if (n == 2 or n == 3):
        return True
    if (n % 2 == 0):
        return False
    k = 0
    q = n - 1
    while( q % 2 == 0):
        k = k + 1
        q = q >> 1


    for i in range(20):                  #重复20次
        a = randint(2, n - 2)
        if( qexp(a, q, n) == 1):
            continue


        mi = qexp(a, q, n)
        flag = 0
        for j in range(k):
            if( mi == (n - 1) ):
                flag = 1
                break
            mi = (mi * mi) % n
        if( flag):
            continue
        return False
    return True



if(__name__ == '__main__'):
    print(miller(2 ^ 127 + 1))